#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <cstring>

using namespace std;

class Trie {
public:
    Trie() {
        end = false;
        memset(children, 0, 26*sizeof(Trie *));
    }
    
    void insert(const char *str)
    {
        Trie *dict = this;
        while(*str) {
            int index = *str - 'a';
            if (dict->children[index] == NULL) {
                dict->children[index] = new Trie();    
            }
            dict = dict->children[index];
            str++;
        }
        dict->end = true;
    }

    bool end;
    Trie *children[26];
};

int dx[] = {0, 1, 0, -1, -1, -1, 1, 1};
int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

void dfs(char *str[], int i, int j, int rows, int cols, Trie *dict, bool used[100][100],  set<string> &answer, string curStr)
{
   if (i < 0 || j < 0 || i >= rows || j >= cols) return; 

   if (used[i][j]) return;

   char ch = str[i][j];
   if (!dict->children[ch-'a']) 
       return;

    dict = dict->children[ch-'a'];

    used[i][j] = true;
    curStr += ch;
    if (dict->end) {
        answer.insert(curStr);
        cout << curStr << endl;
    }

    for (int k = 0; k < 8; k++) {
        dfs(str, i+dx[k], j+dy[k], rows, cols, dict, used, answer, curStr);
    }

    used[i][j] = false;
}


vector<string> findBoggle(char *str[], int rows, int cols, Trie *dict)
{
    bool used[100][100] = {false};
    set<string> answer;
    vector<string> ans;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            dfs(str, i, j, rows, cols, dict, used, answer, "");
        }
    }
    return ans;
}


int main(int argc, char **argv)
{
    char *str[] = {"aelenche",
                   "sdfcsdec",
                   "decbecez",
                   "poevndqc",
                   "ceetcbwe",
                   "qdcurcec",
                   "mndswece",
                   "poqwecec"};

    char *word[] = {"kkjdkjf",
                   "adeevecs",
                    "ec",
                   "nsencr",
                   "pncteec"};

    Trie *dict = new Trie();
    for (int i = 0; i < sizeof(word)/sizeof(char*); i++)
        dict->insert(word[i]);
    
    vector<string> answers = findBoggle(str, 8, 8, dict);
    
    cout << "-----------------Test 1--------------------" << endl;


    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
